/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var marked = new Array();
var exist = function(board, word) {
    if (!board.length) {
        return false;
    }
    var row = board.length;
    var col = board[0].length;
    marked = [...Array(row).keys()].map(() => Array(col).fill(false));
    for(var i = 0; i < row; i++) {
        for(var j = 0; j < col; j++) {
            if (board[i][j] === word[0]) {
                marked[i][j] = true
                // backTrack
                if (backTrack(i, j, board, word.slice(1))) {
                    return true;
                } else {
                    marked[i][j] = false
                }
            }
        }
    }
    return false;
};

var directions = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1],
]
var backTrack = function (i, j,board, word) {
    if (word.length === 0) {
        return true;
    }
    
    for(var x = 0; x < directions.length; x++) {
        var curI = i + directions[x][0];
        var curJ = j + directions[x][1];
        if (curI >= 0 && curI < board.length && curJ >= 0 && curJ < board[0].length 
            && board[curI][curJ] === word[0]
            ) 
        {
            if (marked[curI][curJ]) {
                continue
            }
            marked[curI][curJ] = true
            if (backTrack(curI, curJ, board, word.slice(1))) {
                return true
            } else {
                marked[curI][curJ] = false
            }
        }
    }
    return false;
}
var board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
exist(board, 'ABCCED');